package 链表;

import com.sun.org.apache.bcel.internal.generic.NEW;

public class 反转链表 {
    public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    //迭代
    public ListNode reverseList(ListNode head) {
       if(head == null || head.next == null) return head;

       ListNode newHead = null;
       ListNode tmp = null;
       while(head!=null){
           tmp = head.next;
           head.next = newHead;
           newHead = head;
           head = tmp;
       }
       return newHead;
    }

    //递归写法
    public ListNode reverseListR(ListNode head) {
        if(head == null || head.next == null) return head;

        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return newHead;
    }
}
